import java.util.ArrayList;
import java.util.List;

//力扣2049 找出三位偶数
public class Solution {
    //法一:暴力枚举法
    /*public int[] findEvenNumbers(int[] digits) {
        int count[] = new int[10];
        for (int x : digits) {
            count[x]++;
        }
        List<Integer> list = new ArrayList<>();
        next:
        for (int i = 100; i < 1000; i += 2) {
            int[] c = new int[10];
            for (int j = i; i > 0; i /= 10) {
                int x = j % 10;
                if(++c[x] > count[x]) {
                    continue next;
                }
            }
            list.add(i);
        }
        return list.stream().mapToInt(i -> i).toArray();
    }*/

    //法二: 回溯
    public int[] findEvenNumbers(int[] digits) {
        int[] count = new int[10];
        for (int x : digits) {
            count[x]++;
        }
        List<Integer> list = new ArrayList<>();
        dfs(0, 0, count, list);
        return list.stream().mapToInt(i -> i).toArray();
    }

    private void dfs(int i , int x , int[] count, List<Integer> list) {
        if(i == 3) {
            list.add(x);
            return;
        }
        //i = 0 表示百位 i = 1 表示十位 i = 2 表示个位 x表示当前正在构造的数字
        for (int j = 0; j < 10; j++) {
            if(count[j] > 0 && (i == 0 && j > 0 || i == 1 || i == 2 && j % 2 == 0)) {
                count[j]--;//消耗一个数字
                dfs(i + 1, x * 10 + j, count, list);
                count[j]++;//复原
            }
        }
    }
}

